package com.zhouyong.leetcode.斐波那契数509;

/**
 * @Author 99
 * @Date 2022/10/8 10:51
 * @Version 1.0
 */
public class Test {

    // 斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
    // F(0) = 0，F(1) = 1
    // F(n) = F(n - 1) + F(n - 2)，其中 n > 1
    // 给定n ，请计算 F(n) 。

    // 示例 1：
    //
    //输入：n = 2
    //输出：1
    //解释：F(2) = F(1) + F(0) = 1 + 0 = 1

    //示例 2：
    //输入：n = 3
    //输出：2
    //解释：F(3) = F(2) + F(1) = 1 + 1 = 2

    public static void main(String[] args) {
        System.out.println(fib(6));
    }

    public static int fib(int n) {

        // 暴力解法 - 递归
//        if (n < 2) {
//            return n;
//        }
//        return fib(n - 1) + fib(n - 2);

        // 使用hashmap - 递归，利用缓存的作用减少大量的重复计算，因为斐波那契数会经常重复计算
//        return fic(n, new HashMap<>());

        // 非递归
        int first = 0;
        int second = 1;
        int result = 0, temp = 0;
        if (n == 1) {
            return 1;
        }
        if (n == 0) {
            return 0;
        }
        while (n-- > 1) {
            result = first + second;
            first = second;
            temp = result;
            second = temp;
        }
        return result;
    }

//    public static int fic(int n, HashMap<Integer, Integer> map) {
//        if (n < 2) {
//            return n;
//        }
//        if (map.containsKey(n)) {
//            return map.get(n);
//        }
//        int a = fic(n - 1, map);
//        int b = fic(n - 2, map);
//        map.put(n, a + b);
//        return a + b;
//    }
}
